package Tree;

import sun.reflect.generics.tree.Tree;

import java.util.Stack;

/**
 *  题目 ： 展开二叉搜索树
 *  题目详述 ：
 *  给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，
 *  使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 */
public class IncreasingBST {
    /**
     * 核心思想 ：
     * （1）即，通过中序遍历递增（从小到大）地获取到二叉搜索树的所有节点
     * （2）通过将所获取到的节点的父节点的右子节点指向当前节点，同时将当前所遍历到的节点的左子节点置为null
     * （由于新构建的二叉搜索树中每个节点都是没有左子节点，有且仅有右子节点）
     *  方法一 ：递归
     *  方法二 ：迭代
     */
    TreeNode prev = null;
    TreeNode first = null;
    public TreeNode increasingBST(TreeNode root) {
        // 1.迭代
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode node = root; // 当前正在遍历的节点
//        TreeNode first = null; // 保存重构建的二叉搜索树的根节点（其实实质上就是二叉搜索树的最左子节点）
//        TreeNode prev = null; // 保存当前正在遍历的节点的父节点
//        while(node != null || !stack.isEmpty()){
//            // 循环结束条件 ： 所正在遍历的节点node不为null || stack（迭代所用来保存父节点的栈）中不为null
//            while(node != null){
//                stack.push(node);
//                node = node.left;
//            }
//            node = stack.pop();
//            // 判断是否为重新构建的二叉搜索树根节点
//            if(prev != null){
//                // 重构二叉搜索树的核心步骤 ：使得前一个节点的右子节点为当前正在遍历的节点
//                prev.right = node;
//            }
//            else {
//                // 说明，此节点为重新构建的二叉搜索树的根节点
//                first = node;
//            }
//            // 无论prev是否为null，需要进行的通用操作
//            prev = node; // 上一个节点保存当前正在遍历的节点
//            // 重构建二叉搜索树的步骤：
//            node.left = null; // 当前节点由于不存在左子节点，所以将重构建的二叉搜索树中的节点的左子节点置为null
//            node = node.right; // 遍历二叉树的右子节点；
//        }
//        return first;

        // 2.递归
        /**
         * 需要注意的是,
         * （1）若是将prev节点和first节点传递进入递归方法中的话，由于Java是值传递，
         *  所以prev在方法内部的修改并不会传递到外部，需要去定义全局变量prev和first节点；
         *  （2）定义全局变量的话，能够使得我们在递归中所改变的值能够在递归过程中被递归方法所获取，
         *  若是传递局部变量的话，在递归到上一层方法中时，可能会出现之前对于prev和first节点所赋予的值失效的问题；
         */
         
        TreeNode node = root;

        dfs(node);
        return first;
    }

    private void dfs(TreeNode node) {
        if (node != null){
            dfs(node.left);
            if (prev != null){
                System.out.println("prev after: " + prev.val);
            }
            if(prev != null){
                prev.right = node;
            }
            else {
                first = node;
            }
            prev = node;
            if (prev != null){
                System.out.println("prev begin: " + prev.val);
            }
            node.left = null;

            dfs(node.right);
        }
    }
}
